<?php
//冒泡
function sort1($arr)
{
    $length = count($arr);
    //通过循环每次比较自己和自己前面一个数的值，每次可以获得到一个最大值，循环多少次就可以少比较多少次
    for ($i=0;$i < $length-1;$i++){
        for ($j=0;$j<$length-$i-1;$j++){
            //当前值比后一个值大则交换两个值的位置
            if ($arr[$j] < $arr[$j+1]){
                $t = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $t;
            }
        }
    }
    return $arr;
}

$arr = [8,7,5,6,3,2,10,25,23];

/*
 排序流程(从大到小)
    第一次外层循环排序 数组9个只需要循环8次，最后一个只需要和倒数第二个比较就可以了
    7 8 5 6 3 2 10 25 23
    7 5 8 6 3 2 10 25 23
    7 5 6 8 3 2 10 25 23
    7 5 6 3 8 2 10 25 23
    7 5 6 3 2 8 10 25 23
    7 5 6 3 2 8 10 25 23
    7 5 6 3 2 8 10 25 23
    7 5 6 3 2 8 10 23 25

    第二次外层循环排序 数组9个只需要循环7次，已经可以确认最后一个是数组最大的数了(剩下就是每次排序了)
    5 7 6 3 2 8 10 23 25
    5 6 7 3 2 8 10 23 25
    5 6 3 7 2 8 10 23 25
    5 6 3 2 7 8 10 23 25
    5 6 3 2 7 8 10 23 25
    5 6 3 2 7 8 10 23 25
    5 6 3 2 7 8 10 23 25
 */

//选择排序
//每次循环找到最大的数放到
function sort2($arr)
{
    $length = count($arr);
    for ($i = 0; $i < $length -1; $i++) {
        $minKey = $i;
        for ($j = $i+1 ; $j < $length; $j++) {
            if ($arr[$minKey] > $arr[$j]) {
                $minKey = $j;
            }
        }
        //将本次最小的值交换位置
        $t = $arr[$i];
        $arr[$i] = $arr[$minKey];
        $arr[$minKey] = $t;
    }
    return $arr;
}
//var_dump(sort2($arr));

//数组最小值
function minArr($arr){
    $count = count($arr);
    $min = $arr[0];
    for ($i=0;$i<$count;$i++){
        if ($min > $arr[$i]){
            $min = $arr[$i];
        }
    }
    return $min;
}
//var_dump(minArr($arr));
//数组最大值
function maxArr($arr){
    $count = count($arr);
    $min = $arr[0];
    for ($i=0;$i<$count;$i++){
        if ($min < $arr[$i]){
            $min = $arr[$i];
        }
    }
    return $min;
}


//插入排序
/**
 * @param $arr
 * @return mixed
 * 每次排序将本次排序的数的前面的值进行比较，只要比前面的值大或者小，就将这个值向后移一位，一位本次排序前面的数都是已经排好序的，所以找到满足条件的位置，将本次排序的值放到该位置即可
 */
function sort3($arr)
{
    $count = count($arr);
    for($i=0;$i<$count;$i++){
        $key = $i-1;//与前面的数比较
        $value = $arr[$i];//当前值
        while($key>=0 && $arr[$key]>$value){//第一个数不需要操作
            $arr[$key+1] = $arr[$key];//后移一位
            $key--;
        }
        $arr[$key+1] = $value;//多自减了一次，加回来
    }
    return $arr;
}


//快速排序
function quickSort($arr)
{
    //判断参数是否是一个数组
    if (!is_array($arr)) return false;
    //递归出口:数组长度为1，直接返回数组
    $length = count($arr);
    if ($length <= 1) return $arr;
    //数组元素有多个,则定义两个空数组
    $left = $right = array();
    //使用for循环进行遍历，把第一个元素当做比较的对象
    for ($i = 1; $i < $length; $i++) {
        //判断当前元素的大小
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    //递归调用
    $left = quickSort($left);
    $right = quickSort($right);
    //将所有的结果合并
    return array_merge($left, array($arr[0]), $right);
}




function maoPao3($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tem = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tem;
            }
        }
    }
    return $arr;
}


function change3($arr){
    $length = count($arr);
    if ($length<=0){
        return false;
    }
    for ($i=0;$i<$length-1;$i++){
        $maxKey = $i;
        for ($j=$i;$j<$length;$j++){
            if ($arr[$j] < $arr[$maxKey]){
                $maxKey = $j;
            }
        }
        $tem = $arr[$i];
        $arr[$i] = $arr[$maxKey];
        $arr[$maxKey] = $tem;
    }
    return $arr;
}


function insert3($arr)
{
    $length = count($arr);
    if ($length <= 0){
        return false;
    }
    for ($i = 0; $i < $length; $i++) {
        $key = $i - 1;//与前面的每一个比较
        $value = $arr[$i];
        while ($i >= 0 && $arr[$key] > $value) {
            $arr[$key + 1] = $arr[$key];
            $key--;
        }
        $arr[$key + 1] = $value;
    }
    return $arr;
}

function quickSort3($arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr; //出口
    }
    $left = $right = [];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    $leftArr = quickSort3($left);
    $rightArr = quickSort3($right);
    return array_merge($leftArr, [$arr[0]], $rightArr);
}

function halfFind3($x, $arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    $min = 0;
    $max = $length - 1;
    while ($min <= $max) {
        $middle = intval(($min + $max) / 2);
        if ($x > $arr[$middle]) {
            $min = $middle + 1;
        } elseif ($x < $arr[$middle]) {
            $max = $middle - 1;
        } else {
            return $middle;
        }
    }
    return false;
}

$arr = [1,2,3,4,6,7,9,11,13];

echo halfFind3(13,$arr);